class Node {
  constructor(name) {
    this.name = name;
    this.parent = null;
    this.children = [];
  }

  addChild(node) {
    node.parent = this;
    this.children.push(node);
    return this;
  }

  siblings() {
    const self = this;
    if (this.parent) {
      return this.parent.children.filter(node => node !== self);
    } else {
      return [];
    }
  }

  get degree() {
    return this.children.length;
  }

  getDepthByRoot(root) {
    let depth = 0;
    let currNode = this;
    while (currNode.parent !== root) {
      depth++;
      currNode = currNode.parent;
    }
    return depth + 1;
  }

  get depth() {
    return this.getDepthByRoot(null) - 1;
  }

  get height() {
    // BFS
    const queue = [this];
    let deepestNode = this;

    while (queue.length > 0) {
      const len = queue.length;
      for (let i = 0; i < len; ++i) {
        const currNode = queue.shift();
        deepestNode = currNode;
        if (currNode.children.length > 0) {
          queue.push(...currNode.children);
        }
      }
    }
    return deepestNode.getDepthByRoot(this);
  }

  toString(join = true) {
    let parts = [this.name];
    if (this.children.length > 0) {
      parts = parts.concat(
        this.children
          .map(child => child.toString(false))
          .reduce((left, right) => left.concat(right))
          .map(line => '  ' + line)
      );
    }
    if (join) {
      return parts.join('\n');
    } else {
      return parts;
    }
  }
}

class Tree {
  constructor(root) {
    this.root = root;
  }

  addNode(node, parent = this.root) {
    parent.addChild(node);
    return this;
  }

  search(validator) {
    // DFS
    const queue = [this.root];
    const result = [];
    while (queue.length > 0) {
      const currNode = queue.shift();
      if (validator(currNode)) {
        result.push(currNode);
        continue;
      }
      if (currNode.children.length > 0) {
        queue.unshift(...currNode.children);
      }
    }
    return result;
  }

  size(DFS = true) {
    let size = 0;
    const bag = [this.root];
    while (bag.length > 0) {
      const currNode = bag.shift();
      size++;
      if (currNode.children.length > 0) {
        if (DFS) {
          bag.unshift(...currNode.children);
        } else {
          bag.push(...currNode.children);
        }
      }
    }
    return size;
  }

  get height() {
    return this.root.height;
  }

  toString() {
    return this.root.toString();
  }
}
